package 力扣._474_1和0;

public class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //可看做为0/1背包，该背包容量有两种属性，m个0，n个1，要同时满足两个限制
        //物品重量与价值等价，都为1，方便计数
        int[] w_1 = new int[strs.length];
        int[] w_0 = new int[strs.length];
        for (int i = 0; i < strs.length; i++) {
            int len = strs[i].length();
            int sum_0 = 0;
            for (int j = 0; j < len; j++) {
                if (strs[i].charAt(j) == '0')
                    sum_0++;
            }
            w_0[i] = sum_0;
            w_1[i] = len - sum_0;
        }
        //dp[i][j]: 装满i个0，j个1的容量的背包最多装dp[i][j]个物品
        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 0;

        for (int i = 0; i < strs.length; i++) {    //物品
            for (int j = m; j >= w_0[i]; j--) {     //0
                for (int k = n; k >= w_1[i]; k--) { //1
                    dp[j][k] = Math.max(dp[j][k], dp[j - w_0[i]][k - w_1[i]] + 1);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String[] strs = new String[]{"10", "0001", "111001", "1", "0"};
        int m = 5;
        int n = 3;
        int maxForm = new Solution().findMaxForm(strs,m,n);
        System.out.println(maxForm);
    }
}

